
\subsection{递归}

介绍分治之前，首先要弄清楚递归这个概念。

递归是什么呢？举个简单的例子：从前有座山，山上有座庙，庙里有个老和尚，老和尚给小和尚讲故事：“从前有座山，山上有座庙，庙里有个老和尚，老和尚给小和尚讲故事：‘从前有座山......’” 这个故事与递归算法有着异曲同工之妙。

递归的基本思想是某个函数直接或者间接地调用自身，这样就把原问题的求解转换为许多性质相同但是规模更小的子问题。我们只需要关注如何把原问题划分成符合条件的子问题，而不需要去研究这个子问题是如何被解决的。

递归和枚举的区别在于：枚举是横向地把问题划分，然后依次求解子问题，而递归是把问题逐级分解，是纵向的拆分。

\subsubsection{递归三要素}

在用递归思想解题的时候，要考虑三个要素。

\paragraph{递归式}

如何将原问题划分为子问题？如何科学地进行递归？

\paragraph{递归出口}

终止的条件是什么？换言之，最小的子问题是怎么求解的。

出口可以不止一个。

\paragraph{界函数}

我们用一个函数来表示问题规模变化，这个函数需要保证递归的条件是在像出口条件靠拢。

\paragraph{递归模板}

\begin{cppcode}
int f(传入数值) {
  if (终止条件) return 最小子问题解;
  return f(缩小规模);
}
\end{cppcode}

\subsubsection{递归优化}

先来一道例题：\href{https://www.luogu.org/problemnew/show/P1618}{三连击}。

这道题朴素的递归写法只能得到 25 分，因为递归次数太多，所以超时。

怎么优化呢？详见  搜索优化  和  记忆化搜索 。

\subsection{分治}

分治是一种极为重要的思想。顾名思义，分而治之，就是把大问题化小，再各个击破的过程。

英文名是 divide and conquer.

\begin{NOTE}{例题}{}
求数列中有多少个逆序对，所谓逆序对，是满足 $i < j$ 而且 $a[i] > a[j]$ 的数对 $(i, j)$ 的个数。

\end{NOTE}


考虑把数列等分成两部分，那么原数列的逆序对有两种情况：一种是两个数完全包含在某一侧的子数列中，另一种是两个数一左一右被分开了。

不难发现前者只需要递归地求出，后者只需要对于左侧的每个数，统计右侧有多少个比它小的。
